package com.leetcode.partition5;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/8/10 10:56
 */
public class LC494目标和 {

    public static int findTargetSumWays(int[] nums, int target) {
        return dynamicProgramming(nums, target);
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 1, 1};
        int target = 3;
        System.out.println(findTargetSumWays(nums, target));
    }

    /**
     * 转换为01背包问题，将数组分为两部分，positive和negative，其中positive使用正号，negative使用负号。
     * 要求 sum(positive)-sum(negative)=target，且已知正数和加负数和为数组和 sum(negative)+sum(positive)=sum
     * sum(positive)-sum(negative)+sum(positive)+sum(negative)=target+sum
     * sum(positive)=(target+sum)/2=capacity
     * 问题就转化成了从nums数组选出几个数，使其和等于capacity
     * <p>
     * dp[j]代表了装满容量为j的背包，有dp[j]种方法，因为装满容量为0的背包只有一种方法，因此dp[0]=1
     * 当前j容量的方法数=之前填满容量为j的方法数+之前填满(j-nums[i])种的方法数
     * 状态转移方程式 dp[j]=dp[j]+dp[j-nums[i]]
     */
    private static int dynamicProgramming(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) sum += num;
        //如果全部为正数1的总和都小于1或者推导出来的公式对2求余存在余数不能分为两部分，则直接返回
        if (sum < target || (sum + target) % 2 == 1) return 0;
        int capacity = (target + sum) >> 1;
        int[] dp = new int[capacity + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {     //遍历物品
            for (int j = capacity; j >= nums[i]; j--) {     //遍历容量
                dp[j] = dp[j] + dp[j - nums[i]];
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[capacity];
    }
}
